题解 P1552 [APIO2012]派遣

发表于 | 更新于

题意：$n$个点组成一棵树，每个点都有一个领导力和费用，可以让一个点当领导，然后在这个点的子树中选择一些费用之和不超过$m$的点，得到领导的领导力乘选择的点的个数（领导可不被选择）的利润。求利润最大值。 $n\leqslant100000$；

每个点构造一个大根堆，堆里的就是这个点的人。

往父亲那里合并堆，记录堆的大小，费用的总和。

从儿子合并完毕后，在每个节点，不断踢出费用最大的人，直到费用的总和$\leqslant m$这就是这个点的最优方案了。（显然，花费最小的都留下了）

对于每个点，用这个点的领导力乘堆的大小尝试更新答案即可。

注意：和子树合并的时候,$rt[x]=merge(rt[x],rt[y])$注意是$rt[y]$因为这才是$y$的所属堆的入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define ll long long
#define sqr(x) ((x)*(x))
using namespace std;
inline ll read(){
   ll s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
ll ans,fa[300000],size[300000],p[300000],sum[300000],v[300000],n,m,dist[300000],f[300000],s[2][309009],c[300000],son[2][300000];
ll merge(ll x,ll y){
    if (!x||!y)return x|y;
    if (v[x]<v[y])swap(x,y);
    s[1][x]=merge(s[1][x],y);
    if (dist[s[0][x]]<dist[s[1][x]])swap(s[0][x],s[1][x]);
    dist[x]=dist[s[1][x]]+1;
    return x;
}
int main(){
    n=read(),m=read();
    for (ll i=1;i<=n;++i){
        fa[i]=read();v[i]=read();p[i]=read();
        size[i]=1;sum[i]=v[i];f[i]=i;
        ans=max(ans,p[i]);
    }
    for (ll i=n;i>1;--i){
        ll k=fa[i];
        f[k]=merge(f[i],f[k]);    
        sum[k]+=sum[i];
        size[k]+=size[i];
        while (sum[k]>m){
            sum[k]-=v[f[k]];
            f[k]=merge(s[0][f[k]],s[1][f[k]]);
            --size[k];
        }
        ans=max(ans,p[k]*size[k]);
    }
    printf("%lld",ans);
    return 0;
}